package al03slideWindow;

import java.util.Arrays;
import java.util.HashSet;

public class NotRepeatString {
    // 用位图实现，32位整数，表示当前窗口中字符出现的情况，不如set好用
    public int lengthOfLongestSubstring1(String s) {
        int maxLength = 0;
        HashSet<String> hashSet = new HashSet<>();// 32位整数，表示当前窗口中字符出现的情况
        int left = 0;  // 左指针

//        for (int right = 0; right < s.length(); right++) {
//            // 获取当前字符对应的位位置
//            int charIndex = s.charAt(right);
//
//            // 如果当前字符已经在窗口中出现过，调整左指针
//            while (hashSet.contains(s.charAt(right))) {
//                // 移动左指针，并清除对应位
//                int leftCharIndex = s.charAt(left) - '0';
//                hashSet.clear();
//                left++;  // 左指针右移
//            }
//
//            // 将当前字符的位设置为1，表示该字符已出现
//            hashSet.add(String.valueOf(s.charAt(right)));
//
//            // 更新最大长度
//            maxLength = Math.max(maxLength, right - left + 1);
//        }

        return maxLength;
    }

    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0)
            return 0;

        int maxLength = 0;
        HashSet<Character> hashSet = new HashSet<>();// 32位整数，表示当前窗口中字符出现的情况

        for( int left=0,right=0;right<s.length();right ++ ){

            char currentChar = s.charAt(right);

            while (hashSet.contains(currentChar)){
                hashSet.remove(s.charAt(left));
                left++;
            }
            hashSet.add(currentChar);

            maxLength = Math.max(maxLength, right-left+1);

        }

        return maxLength;
    }

    public int lengthOfLongestSubstring3(String s) {
        if(s.length() == 0)
            return 0;

        int maxLength = 0;
        int[] lastPos = new int[128]; // 假设字符集为ASCII
        Arrays.fill(lastPos, -1); // 初始化为-1，表示字符还未出现过

        for(int left = 0, right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            // 如果字符已经在窗口中，直接将left移到该字符上次出现位置的下一位
            if(lastPos[currentChar] >= left) {
                left = lastPos[currentChar] + 1;
            }

            // 更新字符最后出现的位置
            lastPos[currentChar] = right;

            // 更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }



    public static void main(String[] args) {
        NotRepeatString notRepeatString = new NotRepeatString();
        System.out.println(notRepeatString.lengthOfLongestSubstring3("aabaab!bb"));
    }

}
